package master;

/**
 * 有序链表转换为二叉树
 *
 * @author chenyw
 * @date 2022/8/6 11:08
 */
public class M109sortedListToBST {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        //快慢指针找链表中间节点,pre和p.next将链表分成两段
        ListNode pre = head;
        ListNode p = pre.next;
        ListNode q = p.next;
        //p和q已经先走了一步了
        while (q != null && q.next != null) {
            pre = pre.next;
            p = pre.next;
            q = q.next.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(p.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(p.next);
        return root;
    }
}
